//组合总和三 力扣216
//回溯法
//改进：在对每一层进行处理的时候就顺便计算了本层的sum，回溯时也回溯了sum
//      进行了剪枝操作：1.对于后续元素个数不足的情况进行剪枝
//                      2.对于未选到k个元素但总和已经大于n的情况进行剪枝
class Solution {
private:
	vector<int> path;
	vector<vector<int>> ans;
	void backtracking(int k,int n, int startindex,int sum)
	{
		if(sum > n) return; //剪枝
		if(path.size() == k)
		{
			if(sum == n) ans.push_back(path);
			return;  
		}
		for(int i = startindex; i <= 9-(k-path.size())+1/*剪枝*/; i++)
		{
			path.push_back(i);
			sum += i;
			backtracking(k,n,i+1,sum);
			path.pop_back(); //回溯
			sum -= i; //回溯
		}
	} 
public:
	vector<vector<int>> combinationSum3(int k, int n) {
		backtracking(k,n,1,0);
		return ans;
	}
};
